

/**
 * Created by L.jp
 * Description:输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。
 * 如果该链表长度小于k，请返回一个长度为 0 的链表。
 * User: 86189
 * Date: 2022-05-15
 * Time: 12:54
 */
/*要求：空间复杂度 O(n)，时间复杂度 O(n)
进阶：空间复杂度 O(1)，时间复杂度 O(n)*/
class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val) {
      this.val = val;
   }
}
public class Solution {
    public ListNode FindKthToTail (ListNode pHead, int k) {
        //第一种是使用快慢指针，找到倒数第k个节点
//        if(pHead==null || k==0){
//            return null;
//        }
//        ListNode fast=pHead;
//        ListNode slow=pHead;
//        //先让快指针走k步
//        while (k>0 && fast!=null){
//            fast=fast.next;
//            k--;
//        }
//        //让快慢指针之间相 差k-1个节点
//        while (fast!=null){
//            slow=slow.next;
//            fast = fast.next;
//        }
//        //如果遍历链表结束了，但是k不为0，那么表示k>链表长度，返回null
//        //否则，slow就是倒数第k个节点
//        return k>0 ? null : slow;
        
        //第二种可以顺数找到第n-k个节点
        //先求出链表的长度
        ListNode cur=pHead;
        int n=0;
        //计算长度
        while (cur!=null){
            n++;
            cur = cur.next;
        }
        //找到第n-k个位置
        //先判断k是否合法
        if(n-k<0){
            return null;
        }
        cur=pHead;
        //从头结点的下一个节点开始，遍历n-k次就找到了
        for(int i = 0; i < n-k; i++){
            cur=cur.next;
        }
        return cur;
    }
}
